package org.usmile.algorithms.leetcode.hard;

import java.util.*;

/**
 * 381. O(1) 时间插入、删除和获取随机元素 - 允许重复
 *
 *  RandomizedCollection 是一种包含数字集合(可能是重复的)的数据结构。它应该支持插入和删除特定元素，以及删除随机元素。
 * 实现 RandomizedCollection 类:
 * RandomizedCollection()初始化空的 RandomizedCollection 对象。
 * bool insert(int val) 将一个 val 项插入到集合中，即使该项已经存在。如果该项不存在，则返回 true ，否则返回 false 。
 * bool remove(int val) 如果存在，从集合中移除一个 val 项。如果该项存在，则返回 true ，否则返回 false 。注意，如果 val 在集合中出现多次，我们只删除其中一个。
 * int getRandom() 从当前的多个元素集合中返回一个随机元素。每个元素被返回的概率与集合中包含的相同值的数量 线性相关 。
 * 您必须实现类的函数，使每个函数的 平均 时间复杂度为 O(1) 。
 *
 * 注意：生成测试用例时，只有在 RandomizedCollection 中 至少有一项 时，才会调用 getRandom 。
 *
 * 示例 1:
 * 输入
 * ["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"]
 * [[], [1], [1], [2], [], [1], []]
 * 输出
 * [null, true, false, true, 2, true, 1]
 * 解释
 * RandomizedCollection collection = new RandomizedCollection();// 初始化一个空的集合。
 * collection.insert(1);   // 返回 true，因为集合不包含 1。
 *                         // 将 1 插入到集合中。
 * collection.insert(1);   // 返回 false，因为集合包含 1。
 *                         // 将另一个 1 插入到集合中。集合现在包含 [1,1]。
 * collection.insert(2);   // 返回 true，因为集合不包含 2。
 *                         // 将 2 插入到集合中。集合现在包含 [1,1,2]。
 * collection.getRandom(); // getRandom 应当:
 *                         // 有 2/3 的概率返回 1,
 *                         // 1/3 的概率返回 2。
 * collection.remove(1);   // 返回 true，因为集合包含 1。
 *                         // 从集合中移除 1。集合现在包含 [1,2]。
 * collection.getRandom(); // getRandom 应该返回 1 或 2，两者的可能性相同。
 *
 * 提示:
 * -231 <= val <= 231 - 1
 * insert, remove 和 getRandom 最多 总共 被调用 2 * 105 次
 * 当调用 getRandom 时，数据结构中 至少有一个 元素
 */
public class _0381 {
}

class _0381_Solution {
    private static class RandomizedCollection {
        private final Map<Integer, Set<Integer>> idxMap;
        private final List<Integer> nums;
        private final Random rand = new Random();

        public RandomizedCollection() {
            this.nums = new ArrayList<>();
            this.idxMap = new HashMap<>();
        }

        public boolean insert(int val) {
            Set<Integer> indexes = idxMap.getOrDefault(val, new HashSet<>());
            indexes.add(nums.size());
            idxMap.put(val, indexes);
            nums.add(val);

            return indexes.size() == 1;
        }

        public boolean remove(int val) {
            if (!idxMap.containsKey(val)) {
                return false;
            }

            // 拿到需要删除的元素在列表中的索引位置
            Iterator<Integer> indexes = idxMap.get(val).iterator();
            int index = indexes.next();

            // 将列表中的最后一个元素覆盖掉需要删除的元素
            int lastNum = nums.get(nums.size() - 1);
            nums.set(index, lastNum);

            // 维护删除的元素和最后一个元素的索引
            idxMap.get(val).remove(index);
            idxMap.get(lastNum).remove(nums.size() - 1);
            if (index < nums.size() - 1) {
                idxMap.get(lastNum).add(index);
            }
            // 删除数组列表中的最后一个元素
            nums.remove(nums.size() - 1);
            // 从 map 中删除指定的元素
            if (idxMap.get(val).size() == 0) {
                idxMap.remove(val);
            }

            return true;
        }

        /** Get a random element from the set. */
        public int getRandom() {
            return nums.get(rand.nextInt(nums.size()));
        }
    }
}